home *** CD-ROM | disk | FTP | other *** search
/ GameStar 2004 April / Gamestar_61_2004-04_dvdb.iso / DVDStar / Editace / hltp.exe / {app} / Source Code / Zoners Half-Life Tools / hlcsg / brushunion.cpp < prev    next >
C/C++ Source or Header  |  2000-09-12  |  10KB  |  362 lines
  1. #include "csg.h"
  2.  
  3. vec_t           g_BrushUnionThreshold = DEFAULT_BRUSH_UNION_THRESHOLD;
  4.  
  5. static Winding* NewWindingFromPlane(const brushhull_t* const hull, const int planenum)
  6. {
  7.     Winding*        winding;
  8.     Winding*        front;
  9.     Winding*        back;
  10.     bface_t*        face;
  11.     plane_t*        plane;
  12.  
  13.     plane = &g_mapplanes[planenum];
  14.     winding = new Winding(plane->normal, plane->dist);
  15.  
  16.     for (face = hull->faces; face; face = face->next)
  17.     {
  18.         plane = &g_mapplanes[face->planenum];
  19.         winding->Clip(plane->normal, plane->dist, &front, &back);
  20.         delete winding;
  21.  
  22.         if (front)
  23.         {
  24.             delete front;
  25.         }
  26.         if (back)
  27.         {
  28.             winding = back;
  29.         }
  30.         else
  31.         {
  32.             Developer(DEVELOPER_LEVEL_ERROR, "NewFaceFromPlane returning NULL");
  33.             return NULL;
  34.         }
  35.     }
  36.  
  37.     return winding;
  38. }
  39.  
  40. static void     AddFaceToList(bface_t** head, bface_t* newface)
  41. {
  42.     hlassert(newface);
  43.     hlassert(newface->w);
  44.     if (!*head)
  45.     {
  46.         *head = newface;
  47.         return;
  48.     }
  49.     else
  50.     {
  51.         bface_t*        node = *head;
  52.  
  53.         while (node->next)
  54.         {
  55.             node = node->next;
  56.         }
  57.         node->next = newface;
  58.         newface->next = NULL;
  59.     }
  60. }
  61.  
  62. static int      NumberOfHullFaces(const brushhull_t* const hull)
  63. {
  64.     int             x;
  65.     bface_t*        face;
  66.  
  67.     if (!hull->faces)
  68.     {
  69.         return 0;
  70.     }
  71.  
  72.     for (x = 0, face = hull->faces; face; face = face->next, x++)
  73.     {                                                  // counter
  74.     }
  75.  
  76.     return x;
  77. }
  78.  
  79. // Returns false if union of brushes is obviously zero
  80. static void     AddPlaneToUnion(brushhull_t* hull, const int planenum)
  81. {
  82.     bool            need_new_face = false;
  83.  
  84.     bface_t*        new_face_list;
  85.  
  86.     bface_t*        face;
  87.     bface_t*        next;
  88.  
  89.     plane_t*        split;
  90.     Winding*        front;
  91.     Winding*        back;
  92.  
  93.     new_face_list = NULL;
  94.  
  95.     next = NULL;
  96.  
  97.     hlassert(hull);
  98.  
  99.     if (!hull->faces)
  100.     {
  101.         return;
  102.     }
  103.     hlassert(hull->faces->w);
  104.  
  105.     for (face = hull->faces; face; face = next)
  106.     {
  107.         hlassert(face->w);
  108.         next = face->next;
  109.  
  110.         // Duplicate plane, ignore
  111.         if (face->planenum == planenum)
  112.         {
  113.             AddFaceToList(&new_face_list, CopyFace(face));
  114.             continue;
  115.         }
  116.  
  117.         split = &g_mapplanes[planenum];
  118.         face->w->Clip(split->normal, split->dist, &front, &back);
  119.  
  120.         if (front)
  121.         {
  122.             delete front;
  123.             need_new_face = true;
  124.  
  125.             if (back)
  126.             {                                              // Intersected the face
  127.                 delete face->w;
  128.                 face->w = back;
  129.                 AddFaceToList(&new_face_list, CopyFace(face));
  130.             }
  131.         }
  132.         else
  133.         {
  134.             // Completely missed it, back is identical to face->w so it is destroyed
  135.             if (back)
  136.             {
  137.                 delete back;
  138.                 AddFaceToList(&new_face_list, CopyFace(face));
  139.             }
  140.         }
  141.         hlassert(face->w);
  142.     }
  143.  
  144.     FreeFaceList(hull->faces);
  145.     hull->faces = new_face_list;
  146.  
  147.     if (need_new_face && (NumberOfHullFaces(hull) > 2))
  148.     {
  149.         Winding*        new_winding = NewWindingFromPlane(hull, planenum);
  150.  
  151.         if (new_winding)
  152.         {
  153.             bface_t*        new_face = (bface_t*)Alloc(sizeof(bface_t));
  154.  
  155.             new_face->planenum = planenum;
  156.             new_face->w = new_winding;
  157.  
  158.             new_face->next = hull->faces;
  159.             hull->faces = new_face;
  160.         }
  161.     }
  162. }
  163.  
  164. static vec_t    CalculateSolidVolume(const brushhull_t* const hull)
  165. {
  166.     // calculate polyhedron origin
  167.     // subdivide face winding into triangles
  168.  
  169.     // for each face
  170.     // calculate volume of triangle of face to origin
  171.     // add subidivided volume chunk to total
  172.  
  173.     int             x = 0;
  174.     vec_t           volume = 0.0;
  175.     vec_t           inverse;
  176.     vec3_t          midpoint = { 0.0, 0.0, 0.0 };
  177.  
  178.     bface_t*        face;
  179.  
  180.     for (face = hull->faces; face; face = face->next, x++)
  181.     {
  182.         vec3_t          facemid;
  183.  
  184.         face->w->getCenter(facemid);
  185.         VectorAdd(midpoint, facemid, midpoint);
  186.         Developer(DEVELOPER_LEVEL_MESSAGE, "Midpoint for face %d is %f %f %f\n", x, facemid[0], facemid[1], facemid[2]);
  187.     }
  188.  
  189.     inverse = 1.0 / x;
  190.  
  191.     VectorScale(midpoint, inverse, midpoint);
  192.  
  193.     Developer(DEVELOPER_LEVEL_MESSAGE, "Midpoint for hull is %f %f %f\n", midpoint[0], midpoint[1], midpoint[2]);
  194.  
  195.     for (face = hull->faces; face; face = face->next, x++)
  196.     {
  197.         plane_t*        plane = &g_mapplanes[face->planenum];
  198.         vec_t           area = face->w->getArea();
  199.         vec_t           dist = DotProduct(plane->normal, midpoint);
  200.  
  201.         dist -= plane->dist;
  202.         dist = fabs(dist);
  203.  
  204.         volume += area * dist / 3.0;
  205.     }
  206.  
  207.     Developer(DEVELOPER_LEVEL_MESSAGE, "Volume for brush is %f\n", volume);
  208.  
  209.     return volume;
  210. }
  211.  
  212. static void     DumpHullWindings(const brushhull_t* const hull)
  213. {
  214.     int             x = 0;
  215.     bface_t*        face;
  216.  
  217.     for (face = hull->faces; face; face = face->next)
  218.     {
  219.         Developer(DEVELOPER_LEVEL_MEGASPAM, "Winding %d\n", x++);
  220.         face->w->Print();
  221.         Developer(DEVELOPER_LEVEL_MEGASPAM, "\n");
  222.     }
  223. }
  224.  
  225. static bool     isInvalidHull(const brushhull_t* const hull)
  226. {
  227.     int             x = 0;
  228.     bface_t*        face;
  229.  
  230.     vec3_t          mins = { 99999.0, 99999.0, 99999.0 };
  231.     vec3_t          maxs = { -99999.0, -99999.0, -99999.0 };
  232.  
  233.     for (face = hull->faces; face; face = face->next)
  234.     {
  235.         unsigned int    y;
  236.         Winding*        winding = face->w;
  237.  
  238.         for (y = 0; y < winding->m_NumPoints; y++)
  239.         {
  240.             VectorCompareMinimum(mins, winding->m_Points[y], mins);
  241.             VectorCompareMaximum(maxs, winding->m_Points[y], maxs);
  242.         }
  243.     }
  244.  
  245.     for (x = 0; x < 3; x++)
  246.     {
  247.         if ((mins[x] < (-BOGUS_RANGE / 2)) || (maxs[x] > (BOGUS_RANGE / 2)))
  248.         {
  249.             return true;
  250.         }
  251.     }
  252.     return false;
  253. }
  254.  
  255. void            CalculateBrushUnions(const int brushnum)
  256. {
  257.     int             bn, hull;
  258.     brush_t*        b1;
  259.     brush_t*        b2;
  260.     brushhull_t*    bh1;
  261.     brushhull_t*    bh2;
  262.     entity_t*       e;
  263.  
  264.     b1 = &g_mapbrushes[brushnum];
  265.     e = &g_entities[b1->entitynum];
  266.  
  267.     for (hull = 0; hull < 1 /* NUM_HULLS */ ; hull++)
  268.     {
  269.         bh1 = &b1->hulls[hull];
  270.         if (!bh1->faces)                                   // Skip it if it is not in this hull
  271.         {
  272.             continue;
  273.         }
  274.  
  275.         for (bn = brushnum + 1; bn < e->numbrushes; bn++)
  276.         {                                                  // Only compare if b2 > b1, tests are communitive
  277.             b2 = &g_mapbrushes[e->firstbrush + bn];
  278.             bh2 = &b2->hulls[hull];
  279.  
  280.             if (!bh2->faces)                               // Skip it if it is not in this hull
  281.             {
  282.                 continue;
  283.             }
  284.             if (b1->contents != b2->contents)
  285.             {
  286.                 continue;                                  // different contents, ignore
  287.             }
  288.  
  289.             Developer(DEVELOPER_LEVEL_SPAM, "Processing hull %d brush %d and brush %d\n", hull, brushnum, bn);
  290.  
  291.             {
  292.                 brushhull_t     union_hull;
  293.                 bface_t*        face;
  294.  
  295.                 union_hull.bounds = bh1->bounds;
  296.  
  297.                 union_hull.faces = CopyFaceList(bh1->faces);
  298.  
  299.                 for (face = bh2->faces; face; face = face->next)
  300.                 {
  301.                     AddPlaneToUnion(&union_hull, face->planenum);
  302.                 }
  303.  
  304.                 // union was clipped away (no intersection)
  305.                 if (!union_hull.faces)
  306.                 {
  307.                     continue;
  308.                 }
  309.  
  310.                 if (g_developer >= DEVELOPER_LEVEL_MESSAGE)
  311.                 {
  312.                     Log("\nUnion windings\n");
  313.                     DumpHullWindings(&union_hull);
  314.  
  315.                     Log("\nBrush %d windings\n", brushnum);
  316.                     DumpHullWindings(bh1);
  317.  
  318.                     Log("\nBrush %d windings\n", bn);
  319.                     DumpHullWindings(bh2);
  320.                 }
  321.  
  322.  
  323.                 {
  324.                     vec_t           volume_brush_1;
  325.                     vec_t           volume_brush_2;
  326.                     vec_t           volume_brush_union;
  327.                     vec_t           volume_ratio_1;
  328.                     vec_t           volume_ratio_2;
  329.  
  330.                     if (isInvalidHull(&union_hull))
  331.                     {
  332.                         FreeFaceList(union_hull.faces);
  333.                         continue;
  334.                     }
  335.  
  336.                     volume_brush_union = CalculateSolidVolume(&union_hull);
  337.                     volume_brush_1 = CalculateSolidVolume(bh1);
  338.                     volume_brush_2 = CalculateSolidVolume(bh2);
  339.  
  340.                     volume_ratio_1 = volume_brush_union / volume_brush_1;
  341.                     volume_ratio_2 = volume_brush_union / volume_brush_2;
  342.  
  343.                     if ((volume_ratio_1 > g_BrushUnionThreshold) || (g_developer >= DEVELOPER_LEVEL_MESSAGE))
  344.                     {
  345.                         volume_ratio_1 *= 100.0;
  346.                         Warning("Entity %d : Brush %d intersects with brush %d by %2.3f percent", b1->entitynum,
  347.                                 brushnum, bn, volume_ratio_1);
  348.                     }
  349.                     if ((volume_ratio_2 > g_BrushUnionThreshold) || (g_developer >= DEVELOPER_LEVEL_MESSAGE))
  350.                     {
  351.                         volume_ratio_2 *= 100.0;
  352.                         Warning("Entity %d : Brush %d intersects with brush %d by %2.3f percent", b1->entitynum, bn,
  353.                                 brushnum, volume_ratio_2);
  354.                     }
  355.                 }
  356.  
  357.                 FreeFaceList(union_hull.faces);
  358.             }
  359.         }
  360.     }
  361. }
  362.